home *** CD-ROM | disk | FTP | other *** search
/ Libris Britannia 4 / science library(b).zip / science library(b) / TECHNICA / COMPUTER / H254.ZIP / IRITSM3S.ZIP / IRIT / CONVEX.C < prev    next >
C/C++ Source or Header  |  1992-02-25  |  19KB  |  551 lines
  1. /*****************************************************************************
  2. *   "Irit" - the 3d polygonal solid modeller.                     *
  3. *                                         *
  4. * Written by:  Gershon Elber                Ver 0.2, Mar. 1990   *
  5. ******************************************************************************
  6. *   Module to handle convexity of polygons: Test for convexity, and split    *
  7. * none convex polygons into convex ones.                     *
  8. *****************************************************************************/
  9.  
  10. /* #define DEBUG2           Defines some printing/debugging routines. */
  11.  
  12. #ifdef __MSDOS__
  13. #include <alloc.h>
  14. #endif /* __MSDOS__ */
  15.  
  16. #include <stdio.h>
  17. #include <ctype.h>
  18. #include <math.h>
  19. #include <string.h>
  20. #include "program.h"
  21. #include "allocate.h"
  22. #include "booleang.h"
  23. #include "convex.h"
  24. #include "geomat3d.h"
  25. #include "graphgen.h"
  26. #include "intrnrml.h"
  27. #include "objects.h"
  28. #include "priorque.h"
  29. #include "windows.h"
  30.  
  31. /* Used to hold edges (V | V -> Pnext) that intersect with level y = Ylevel. */
  32. typedef struct InterYVrtxList {
  33.     ByteType InterYType;
  34.     VertexStruct *V;
  35.     struct InterYVrtxList *Pnext;
  36. } InterYVrtxList;
  37.  
  38. #define CONVEX_EPSILON  1e-4       /* Colinearity of two normalized vectors. */
  39.  
  40. #define    INTER_Y_NONE    0               /* Y level intersection type. */
  41. #define    INTER_Y_START    1
  42. #define    INTER_Y_MIDDLE    2
  43.  
  44. #define LOOP_ABOVE_Y    0      /* Type of open loops extracted from polygon. */
  45. #define LOOP_BELOW_Y    1
  46.  
  47. /* Used to sort and combine the polygons above Ylevel together if possible.  */
  48. typedef struct SortPolysInX {
  49.     VertexStruct *VMinX, *VMaxX;
  50.     int Reverse;      /* If TRUE than VMinX vertex is AFTER VMaxX vertex. */
  51. } SortPolysInX;
  52.  
  53. /* The following are temporary flags used to mark vertices that were visited */
  54. /* by the loop tracing, at list once. As each vertex may be visited two at   */
  55. /* the most (as starting & as end point of open loop), this is enough.         */
  56. /* INTER_TAG is used to mark vertices that created brand new with intersected*/
  57. /* with the line y = Ylevel. Those are used to detect INTERNAL edges - if    */
  58. /* at list one end of it is INTER_TAG, that edge is INTERNAL (see Irit.h).   */
  59. #define INTER_TAG   0x40
  60. #define VISITED_TAG 0x80
  61.  
  62. #define    IS_INTER_VRTX(Vrtx)    ((Vrtx)->Tags & INTER_TAG)
  63. #define    SET_INTER_VRTX(Vrtx)    ((Vrtx)->Tags |= INTER_TAG)
  64. #define    RST_INTER_VRTX(Vrtx)    ((Vrtx)->Tags &= ~INTER_TAG)
  65.  
  66. #define    IS_VISITED_VRTX(Vrtx)    ((Vrtx)->Tags & VISITED_TAG)
  67. #define    SET_VISITED_VRTX(Vrtx)    ((Vrtx)->Tags |= VISITED_TAG)
  68. #define    RST_VISITED_VRTX(Vrtx)    ((Vrtx)->Tags &= ~VISITED_TAG)
  69.  
  70. static int SplitPolyIntoTwo(PolygonStruct *Pl, VertexStruct *V,
  71.                 PolygonStruct **Pl1, PolygonStruct **Pl2);
  72. static VertexStruct *FindRayPolyInter(PolygonStruct *Pl,
  73.         VertexStruct *VRay, PointType RayDir, PointType PInter);
  74. static void TestConvexityDir(PolygonStruct *Pl);
  75.  
  76. #ifdef DEBUG2
  77. static void PrintVrtxList(VertexStruct *V);
  78. static void PrintPoly(PolygonStruct *P);
  79. #endif /* DEBUG2 */
  80.  
  81. /*****************************************************************************
  82. *   Routine to prepare transformation martix to rotate such that Dir is         *
  83. * parallel to the Z axes. Used by the convex decomposition to rotate the     *
  84. * polygons to be XY plane parallel.                         *
  85. *    Algorithm: form a 4 by 4 matrix from Dir as follows:             *
  86. *                |  Tx  Ty  Tz  0 |   A transformation which takes the coord *
  87. *                |  Bx  By  Bz  0 |  system into T, N & B as required.         *
  88. * [X  Y  Z  1] * |  Nx  Ny  Nz  0 |                         *
  89. *                |  0   0   0   1 |                         *
  90. * N is exactly Dir, but we got freedom on T & B - T & B must be on         *
  91. * a plane perpendicular to N and perpendicular between them but thats all!   *
  92. * T is therefore selected using this (heuristic ?) algorithm:             *
  93. * Let P be the axis of which the absolute N coefficient is the smallest.     *
  94. * Let B be (N cross P) and T be (B cross N).                     *
  95. *****************************************************************************/
  96. void GenRotateMatrix(MatrixType Mat, VectorType Dir)
  97. {
  98.     int i, j;
  99.     RealType R;
  100.     VectorType DirN, T, B, P;
  101.  
  102.     PT_COPY(DirN, Dir);
  103.     PT_NORMALIZE(DirN);
  104.     PT_CLEAR(P);
  105.     for (i = 1, j = 0, R = ABS(DirN[0]); i < 3; i++) if (R > ABS(DirN[i])) {
  106.     R = DirN[i];
  107.     j = i;
  108.     }
  109.     P[j] = 1.0;/* Now P is set to the axis with the biggest angle from DirN. */
  110.  
  111.     VecCrossProd(B, DirN, P);                  /* calc the bi-normal. */
  112.     PT_NORMALIZE(B);
  113.     VecCrossProd(T, B, DirN);                /* calc the tangent. */
  114.  
  115.     MatGenUnitMat(Mat);
  116.     for (i = 0; i < 3; i++) {
  117.     Mat[i][0] = T[i];
  118.     Mat[i][1] = B[i];
  119.     Mat[i][2] = DirN[i];
  120.     }
  121. }
  122.  
  123. /*****************************************************************************
  124. *   Routine to test all polygons in a given object for convexity, and split  *
  125. * non convex ones, non destructively - the original object is not modified.  *
  126. *****************************************************************************/
  127. ObjectStruct *ConvexPolyObjectN(ObjectStruct *PObj)
  128. {
  129.     ObjectStruct *PObjCopy;
  130.  
  131.     PObjCopy = CopyObject(NULL, PObj, FALSE);
  132.     ConvexPolyObject(PObjCopy);
  133.  
  134.  
  135.     return PObjCopy;
  136. }
  137.  
  138. /*****************************************************************************
  139. *   Routine to test all the polygons in a given object for convexity, and    *
  140. * split the non convex ones.                             *
  141. *****************************************************************************/
  142. void ConvexPolyObject(ObjectStruct *PObj)
  143. {
  144.     PolygonStruct *Pl, *PlSplit, *PlTemp,
  145.     *PlPrev = NULL;
  146.  
  147.     if (!IS_POLY_OBJ(PObj))
  148.     FatalError("ConvexPolyObject: parameter given is not polygonal object");
  149.  
  150.     if (IS_POLYLINE_OBJ(PObj)) {
  151.     WndwInputWindowPutStr("ConvexPolyObject: polyline object ignored");
  152.     return;
  153.     }
  154.  
  155.     Pl = PObj -> U.Pl.P;
  156.     while (Pl != NULL) {
  157.     if (!ConvexPolygon(Pl)) {
  158.         PlSplit = SplitNonConvexPoly(Pl);
  159.         CleanUpPolygonList(&PlSplit);       /* Zero length edges etc. */
  160.         if (PlSplit != NULL) {     /* Something is wrong here, ignore. */
  161.         if (Pl == PObj -> U.Pl.P)
  162.             PObj -> U.Pl.P = PlSplit;               /* First. */
  163.         else
  164.             PlPrev -> Pnext = PlSplit;
  165.  
  166.         PlTemp = PlSplit;
  167.         while (PlTemp -> Pnext != NULL) PlTemp = PlTemp -> Pnext;
  168.         PlTemp -> Pnext = Pl -> Pnext;
  169.         PlPrev = PlTemp;
  170.  
  171.         Pl -> Pnext = NULL;
  172.         MyFree((char *) Pl, ALLOC_POLYGON);    /* Free old polygon. */
  173.         Pl = PlPrev -> Pnext;
  174.         }
  175.         else {
  176.         if (Pl == PObj -> U.Pl.P) PObj -> U.Pl.P = Pl -> Pnext;
  177.         PlPrev = Pl -> Pnext;
  178.         Pl -> Pnext = NULL;
  179.         MyFree((char *) Pl, ALLOC_POLYGON);    /* Free old polygon. */
  180.         Pl = PlPrev;
  181.         }
  182.     }
  183.     else {
  184.         PlPrev = Pl;
  185.         Pl = Pl -> Pnext;
  186.     }
  187.     }
  188. }
  189.  
  190. /*****************************************************************************
  191. *   Routine to test if the given polygon is convex or not.             *
  192. * Algorithm: The polygon is convex iff the normals generated from cross      *
  193. * products of two consecutive edges points to the same direction. he same    *
  194. * direction is tested by dot product with the polygon plane normal which     *
  195. * should produce consistent sign for all normals, in order the polygon to    *
  196. * be convex.                                     *
  197. *   The routine returns TRUE iff the polygon is convex. In addition the      *
  198. * polygon CONVEX tag (see Irit.h) is also updated.                 *
  199. *   Note that if the polygon IS marked as convex, nothing is tested!         *
  200. *   Also convex polygons are tested so that the vertices are ordered such    *
  201. * that cross product of two adjacent edges will be in the normal direction.  *
  202. *****************************************************************************/
  203. int ConvexPolygon(PolygonStruct *Pl)
  204. {
  205.     int FirstTime = TRUE;
  206.     RealType NormalSign, Size;
  207.     VectorType V1, V2, PolyNormal, Normal;
  208.     VertexStruct *VNext,
  209.     *V = Pl -> V;
  210.  
  211.     if (IS_CONVEX_POLY(Pl)) return TRUE;       /* Nothing to do around here. */
  212.  
  213.     /* Copy only A, B, C from Ax+By+Cz+D = 0: */
  214.     PT_COPY(PolyNormal, Pl -> Plane);
  215.  
  216.     do {
  217.     VNext = V -> Pnext;
  218.  
  219.     PT_SUB(V1, VNext -> Pt, V -> Pt);
  220.     if ((Size = PT_LENGTH(V1)) > EPSILON) {
  221.         Size = 1.0 / Size;
  222.         PT_SCALE(V1, Size);
  223.     }
  224.     PT_SUB(V2, VNext -> Pnext -> Pt, VNext -> Pt);
  225.     if ((Size = PT_LENGTH(V2)) > EPSILON) {
  226.         Size = 1.0 / Size;
  227.         PT_SCALE(V2, Size);
  228.     }
  229.     VecCrossProd(Normal, V1, V2);
  230.  
  231.     if (PT_LENGTH(Normal) < CONVEX_EPSILON) {
  232.         V = VNext;
  233.         continue;                    /* Skip colinear points. */
  234.     }
  235.  
  236.     if (FirstTime) {
  237.         FirstTime = FALSE;
  238.         NormalSign = DOT_PROD(Normal, PolyNormal);
  239.     }
  240.     else if (NormalSign * DOT_PROD(Normal, PolyNormal) < 0.0) {
  241.         RST_CONVEX_POLY(Pl);
  242.         return FALSE;          /* Different signs --> not convex. */
  243.     }
  244.  
  245.     V = VNext;
  246.     }
  247.     while (V != Pl -> V);
  248.  
  249.     SET_CONVEX_POLY(Pl);
  250.  
  251.     if (NormalSign < 0.0) ReverseVrtxList(Pl);
  252.  
  253.     return TRUE;    /* All signs are the same --> the polygon is convex. */
  254. }
  255.  
  256. /*****************************************************************************
  257. *   Routine to split non convex polygon to list of convex ones.             *
  258. * This algorithm is much simpler than the one used before:             *
  259. * 1. Remove a polygon from GlblList. If non exists stop.             *
  260. * 2. Search for non convex corner. If not found stop - polygon is convex.    *
  261. *    Otherwise let the non convex polygon found be V(i).             *
  262. * 3. Fire a ray from V(i) in the opposite direction to V(i-1). Find the      *
  263. *    closest intersection of the ray with polygon boundary P.             *
  264. * 4. Split the polygon into two at V(i)-P edge and push the two new polygons *
  265. *    on the GlblList.                                 *
  266. * 5. Goto 1.                                     *
  267. *****************************************************************************/
  268. PolygonStruct *SplitNonConvexPoly(PolygonStruct *Pl)
  269. {
  270.     int IsConvex;
  271.     RealType Size;
  272.     PolygonStruct *GlblList, *Pl1, *Pl2,
  273.     *GlblSplitPl = NULL;
  274.     VectorType V1, V2, PolyNormal, Normal;
  275.     VertexStruct *V, *VNext;
  276.  
  277.     TestConvexityDir(Pl);
  278.  
  279.     GlblList = AllocPolygon(0, 0, CopyVList(Pl -> V), NULL);
  280.     PLANE_COPY(GlblList -> Plane, Pl -> Plane);
  281.  
  282.     /* Copy only A, B, C from Ax+By+Cz+D = 0 plane equation: */
  283.     PT_COPY(PolyNormal, Pl -> Plane);
  284.  
  285.     while (GlblList != NULL) {
  286.     Pl = GlblList;
  287.     GlblList = GlblList -> Pnext;
  288.     Pl -> Pnext = NULL;
  289.  
  290.     IsConvex = TRUE;
  291.     V = Pl -> V;
  292.     do {
  293.         VNext = V -> Pnext;
  294.  
  295.         PT_SUB(V1, VNext -> Pt, V -> Pt);
  296.          if ((Size = PT_LENGTH(V1)) > EPSILON) {
  297.         Size = 1.0 / Size;
  298.         PT_SCALE(V1, Size);
  299.         }
  300.         PT_SUB(V2, VNext -> Pnext -> Pt, VNext -> Pt);
  301.          if ((Size = PT_LENGTH(V2)) > EPSILON) {
  302.         Size = 1.0 / Size;
  303.         PT_SCALE(V2, Size);
  304.         }
  305.         VecCrossProd(Normal, V1, V2);
  306.         if (PT_LENGTH(Normal) < CONVEX_EPSILON) {
  307.         V = VNext;
  308.         continue;                /* Skip colinear points. */
  309.         }
  310.  
  311.         if (DOT_PROD(Normal, PolyNormal) < 0.0 &&
  312.         SplitPolyIntoTwo(Pl, V, &Pl1, &Pl2)) {
  313.         Pl -> V = NULL;          /* Dont free vertices - used in Pl1/2. */
  314.         Pl -> Pnext = NULL;
  315.         MyFree((char *) Pl, ALLOC_POLYGON);
  316.  
  317.         Pl1 -> Pnext = GlblList;       /* Push polygons on GlblList. */
  318.         GlblList = Pl1;
  319.         Pl2 -> Pnext = GlblList;
  320.         GlblList = Pl2;
  321.  
  322.         IsConvex = FALSE;
  323.         break;
  324.         }
  325.  
  326.         V = VNext;
  327.     }
  328.     while (V != Pl -> V);
  329.  
  330.     if (IsConvex) {
  331.         SET_CONVEX_POLY(Pl);
  332.         Pl -> Pnext = GlblSplitPl;
  333.         GlblSplitPl = Pl;
  334.     }
  335.     }
  336.  
  337.     return GlblSplitPl;
  338. }
  339.  
  340. /*****************************************************************************
  341. *   Split polygon at the vertex specified by V -> Pnext, given V, into two,  *
  342. * by firing a ray from V -> Pnext in the opposite direction to V and finding *
  343. * closest intersection with the polygon P. (V -> Pnext, P) is the edge to    *
  344. * split the polygon at.                                 *
  345. *****************************************************************************/
  346. static int SplitPolyIntoTwo(PolygonStruct *Pl, VertexStruct *V,
  347.                 PolygonStruct **Pl1, PolygonStruct **Pl2)
  348. {
  349.     PointType Vl, PInter;
  350.     VertexStruct *VInter, *VNew1, *VNew2;
  351.  
  352.     PT_SUB(Vl, V -> Pnext -> Pt, V -> Pt);
  353.     VInter = FindRayPolyInter(Pl, V -> Pnext, Vl, PInter);
  354.     V = V -> Pnext;
  355.  
  356.     if (VInter == NULL ||
  357.     VInter == V ||
  358.     VInter -> Pnext == V)
  359.     return FALSE;
  360.  
  361.     /* Make the two polygon vertices lists. */
  362.     VNew1 = AllocVertex(V -> Count, V -> Tags, NULL, V -> Pnext);
  363.     PT_COPY(VNew1 -> Pt, V -> Pt);
  364.     PT_COPY(VNew1 -> Normal, V -> Normal);
  365.     SET_INTERNAL_EDGE(V);
  366.     if (PT_EQ(VInter -> Pt, PInter)) {
  367.     /* Intersection points is close to VInter point. */
  368.     VNew2 = AllocVertex(VInter -> Count, VInter -> Tags, NULL,
  369.                             VInter -> Pnext);
  370.     PT_COPY(VNew2 -> Pt, VInter -> Pt);
  371.     PT_COPY(VNew2 -> Normal, VInter -> Normal);
  372.     VInter -> Pnext = VNew1;
  373.     SET_INTERNAL_EDGE(VInter);
  374.     V -> Pnext = VNew2;
  375.     }
  376.     else if (PT_EQ(VInter -> Pnext -> Pt, PInter)) {
  377.     /* Intersection points is close to VInter -> Pnext point. */
  378.     VNew2 = AllocVertex(VInter -> Pnext -> Count, VInter -> Pnext -> Tags,
  379.                     NULL, VInter -> Pnext -> Pnext);
  380.     PT_COPY(VNew2 -> Pt, VInter -> Pnext -> Pt);
  381.     PT_COPY(VNew2 -> Normal, VInter -> Pnext -> Normal);
  382.     VInter -> Pnext -> Pnext = VNew1;
  383.     SET_INTERNAL_EDGE(VInter -> Pnext);
  384.     V -> Pnext = VNew2;
  385.     }
  386.     else {
  387.     /* PInter is in the middle of (VInter, VInter -> Pnext) edge: */
  388.     VNew2 = AllocVertex(VInter -> Count, VInter -> Tags, NULL,
  389.                             VInter -> Pnext);
  390.     PT_COPY(VNew2 -> Pt, PInter);
  391.     VInter -> Pnext = AllocVertex(0, 0, NULL, VNew1);
  392.     PT_COPY(VInter -> Pnext -> Pt, PInter);
  393.     InterpNrmlBetweenTwo(VNew2, VInter, VNew2 -> Pnext);
  394.     PT_COPY(VInter -> Pnext -> Normal, VNew2 -> Normal);
  395.     SET_INTERNAL_EDGE(VInter -> Pnext);
  396.     V -> Pnext = VNew2;
  397.     }
  398.  
  399.     *Pl1 = AllocPolygon(0, 0, VNew1, NULL);
  400.     PLANE_COPY((*Pl1) -> Plane, Pl -> Plane);
  401.     *Pl2 = AllocPolygon(0, 0, VNew2, NULL);
  402.     PLANE_COPY((*Pl2) -> Plane, Pl -> Plane);
  403.  
  404.     return TRUE;
  405. }
  406.  
  407. /*****************************************************************************
  408. *   Find where a ray first intersect a given polygon. The ray starts at one  *
  409. * of the polygon vertices and so distance less than EPSILON is ignored.      *
  410. *   Returns the vertex V in which (V, V -> Pnext) has the closest         *
  411. * intersection with the ray PRay, DRay at Inter.                 *
  412. *****************************************************************************/
  413. static VertexStruct *FindRayPolyInter(PolygonStruct *Pl,
  414.             VertexStruct *VRay, PointType RayDir, PointType PInter)
  415. {
  416.     RealType t1, t2,
  417.     MinT = INFINITY;
  418.     PointType Vl, Ptemp1, Ptemp2, PRay;
  419.     VertexStruct *VNext,
  420.     *V = Pl -> V,
  421.     *VInter = NULL;
  422.  
  423.     PT_COPY(PRay, VRay -> Pt);
  424.  
  425.     do {
  426.     VNext = V -> Pnext;
  427.     if (V != VRay && VNext != VRay) {
  428.         PT_SUB(Vl, V -> Pnext -> Pt, V -> Pt);
  429.         if (CGDistPointLine(PRay, V -> Pt, Vl) > EPSILON) {
  430.         /* Only if the point the ray is shoot from is not on line: */
  431.         CG2PointsFromLineLine(PRay, RayDir, V -> Pt, Vl, Ptemp1, &t1,
  432.                                  Ptemp2, &t2);
  433.         if (CGDistPointPoint(Ptemp1, Ptemp2) < EPSILON * 10.0 &&
  434.             t1 > EPSILON && t1 < MinT &&
  435.             (t2 <= 1.0 || APX_EQ(t2, 1.0)) &&
  436.             (t2 >= 0.0 || APX_EQ(t2, 0.0))) {
  437.             PT_COPY(PInter, Ptemp2);
  438.             VInter = V;
  439.             MinT = t1;
  440.         }
  441.         }
  442.     }
  443.     V = VNext;
  444.     }
  445.     while (V != Pl -> V);
  446.  
  447.     return VInter;
  448. }
  449.  
  450. /*****************************************************************************
  451. *   Test convexity direction - a cross product of two edges of a convex      *
  452. * corner of the polygon should point in the normal direction. if this is not *
  453. * the case - the polygon vertices are reveresed.                 *
  454. *****************************************************************************/
  455. static void TestConvexityDir(PolygonStruct *Pl)
  456. {
  457.     int Coord = 0;
  458.     VectorType V1, V2, Normal;
  459.     VertexStruct *V, *VExtrem;
  460.  
  461.     /* Find the minimum component direction of the normal and used that axes */
  462.     /* to find an extremum point on the polygon - that extrmum point must be */
  463.     /* a convex corner so we can find the normal direction of convex corner. */
  464.     if (ABS(Pl -> Plane[1]) < ABS(Pl -> Plane[Coord])) Coord = 1;
  465.     if (ABS(Pl -> Plane[2]) < ABS(Pl -> Plane[Coord])) Coord = 2;
  466.     V = VExtrem = Pl -> V;
  467.     do {
  468.     if (V -> Pt[Coord] > VExtrem -> Pt[Coord]) VExtrem = V;
  469.     V = V -> Pnext;
  470.     }
  471.     while (V != Pl -> V);
  472.  
  473.     /* Make sure next vertex is not at the extremum value: */
  474.     while (APX_EQ(VExtrem -> Pt[Coord], VExtrem -> Pnext -> Pt[Coord]))
  475.                         VExtrem = VExtrem -> Pnext;
  476.  
  477.     /* O.K. V form a convex corner - evaluate its two edges cross product:   */
  478.     for (V = Pl -> V; V -> Pnext != VExtrem; V = V -> Pnext);  /* Find Prev. */
  479.     PT_SUB(V1, VExtrem -> Pt, V -> Pt);
  480.     PT_SUB(V2, VExtrem -> Pnext -> Pt, VExtrem -> Pt);
  481.     VecCrossProd(Normal, V1, V2);
  482.  
  483.     if (DOT_PROD(Normal, Pl -> Plane) < 0.0) ReverseVrtxList(Pl);
  484. }
  485.  
  486. /*****************************************************************************
  487. *   Reverse the vertex list of a given polygon. This is used mainly to       *
  488. * reverse polygons such that cross product of consecutive edges which form   *
  489. * a convex corner will point in the polygon normal direction.             *
  490. *****************************************************************************/
  491. void ReverseVrtxList(PolygonStruct *Pl)
  492. {
  493.     ByteType Tags, Count;
  494.     VertexStruct *VNextNext,
  495.     *V = Pl -> V,
  496.     *VNext = V -> Pnext;
  497.  
  498.     do {
  499.     VNextNext = VNext -> Pnext;
  500.     VNext -> Pnext = V;                 /* Reverse the pointer! */
  501.  
  502.     V = VNext;               /* Advance all 3 pointers by one. */
  503.     VNext = VNextNext;
  504.     VNextNext = VNextNext -> Pnext;
  505.     }
  506.     while (V != Pl -> V);
  507.  
  508.     V = Pl -> V;      /* Move the Tags/Count by one - to the right edge. */
  509.     Tags = V -> Tags;
  510.     Count = V -> Count;
  511.     do {
  512.     if (V -> Pnext == Pl -> V) {
  513.         V -> Tags = Tags;
  514.         V -> Count = Count;
  515.     }
  516.     else {
  517.         V -> Tags = V -> Pnext -> Tags;
  518.         V -> Count = V -> Pnext -> Count;
  519.     }
  520.  
  521.     V = V -> Pnext;
  522.     }
  523.     while (V != Pl -> V);
  524. }
  525.  
  526. #ifdef DEBUG2
  527.  
  528. /*****************************************************************************
  529. *   Print the content of the given vertex list, to standard output.         *
  530. *****************************************************************************/
  531. static void PrintPoly(PolygonStruct *P)
  532. {
  533.     VertexStruct
  534.     *VFirst = P -> V,
  535.     *V = VFirst;
  536.  
  537.     if (V == NULL) return;
  538.  
  539.     printf("VERTEX LIST:\n");
  540.     do {
  541.     printf("%12lg %12lg %12lg, Tags = %02x\n",
  542.         V -> Pt[0], V -> Pt[1], V -> Pt[2], V -> Tags);
  543.     V = V -> Pnext;
  544.     }
  545.     while (V != NULL && V != VFirst);
  546.  
  547.     if (V == NULL) printf("Loop is not closed (NULL terminated)\n");
  548. }
  549.  
  550. #endif /* DEBUG2 */
  551.